package 二分;
/**
 *这样的二分还是 有些问题的
 *就是 如果 二分的 值
 *不存在的 话 
 *那么 getLeftIndex  和   getRightIndex 
 *就会出现错误
 */
import java.util.Arrays;

public class leetcode34查找指定元素的开头和结尾 {
	static int ans [] = {-1,-1};
	public static void main(String []args) {
//		int []nums = {5,7,7,8,8,10};
		int nums[] = {1,2,3,4,5,6,7,8,9,10};
		int target = 0;
//		int nums [] = {1};
//		int target = 0;
		//System.out.println(Arrays.toString(solution(nums,target)));
		int index1 = getLeftIndex(nums,target);
		int index2 = getRightIndex(nums,target);
		System.out.println(index1);
		System.out.println(index2);
	//	System.out.println(Arrays.toString(ans));
//		System.out.println(getIndex(nums,0));
	//	System.out.println(Arrays.toString(solutionTwo(nums,target)));
	}
	/**
	 * 时间 复杂度 为 O(3 logN ) 省略掉 常数项 就是           O(logN)
	 * 
	 * 
	 * 
	 */
	
	public static int [] solutionTwo(int nums[],int target) {
//		int ans [] = {-1,-1};
		if(nums.length == 0 || getIndex(nums,target) == -1)
			return new int[] {-1,-1};
		int leftIndex = getLeftIndex(nums,target);
		int  rightIndex = getRightIndex(nums,target);
//		return ans;
		return new int [] {leftIndex,rightIndex};
	}
	
	
	
	/**
	 * 时间复杂度 为 O(N)
	 * 主要 是 一些边界 的处理 逻辑 
	 * 主要的 特殊 案例  有  []  ;,    [1] target 1;  [1,1,1] target ; 这种特殊 案例
	 * 边界的 处理 条件 
	 */
	public static int []  solution(int nums[],int target) {
//		int []  ans = new int [2];
		int [] ans  = {-1,-1};
//		  其实 可以 省掉 这个 index 变量的 直接 赋值 就行 不 就 0 和 1  两个索引
		int index  = 0;
		for(int i = 0;i < nums.length;i++) {
			if(nums[i] == target) {
				ans[index++] = i;
				for(int j = i + 1; j < nums.length; j++ ) {
					/**
					 */
						if(nums[j] != nums[j-1]) {
							ans[index] = j - 1;
							
							return ans;
						}
						/**
						 * 
						 */
						else if(j == nums.length -1){
							ans[index] = j;
							return ans;
						}
				}
				ans[index] = i;
				return ans;
			}
		}
		return ans;
	}
	
	public static int getLeftIndex(int nums[],int value) {
		/**
		 * 用这个 index 记录着 并更新 这个  满足条件的 最左侧的下标
		 * 可以 省去 
		 * 但是 没必要 
		 * 就算 多用  这一个  int 的变量 又不会 死 干嘛 写的 那么  去 扣 coding 的 简洁
		 */
		int index = -1;
		int l = 0 ;
		int r = nums.length - 1;
		int mid = 0;
		while(l <= r) {
			mid = l + ((r - l )>>1);
			/**
			 * 这里 做个 解释   
			 * int arr []= {5,7,7,8,8,10};
			 * value  = 7
			 * 对于上面 的   数组 来说 
			 * 条件是 nums[mid] >= value 时候返回的 是   index 是 1
			 * 而条件 是   nums[mid] > value 的时候 返回的 结果 是 index 是 3
			 * 这就不需要 我多解释了 吧 
			 */
			if(nums[mid] >= value) {
				index = mid;
				r = mid -1;
			}
			else {
				l  = mid + 1;
			}
		}
		ans[0] = index;
		return index;
	}
	public static int getRightIndex(int nums[],int value) {
		int l = 0;
		int r = nums.length - 1;
		int index = -1;
		int mid = 0;
		while(l <= r) {
			mid = l + r >> 1;
		/**
		 * 这里 做个 解释   
		 * int arr []= {5,7,7,8,8,10};
		 * value  = 7
		 * 对于上面 的   数组 来说 
		 * 条件是 nums[mid] <= value 时候返回的 是   index 是 1
		 * 而条件 是   nums[mid] < value 的时候 返回的 结果 是 index 是 0
		 * 这就不需要 我多解释了 吧 
		 */
			if(nums[mid] <= value) {
				index = mid;
				l = mid + 1;
			}
			else {
				r = mid - 1 ;
			}
		}
		ans[1] = index; 
		return index;
	}
	public static int getIndex(int nums[],int target) {
//		int index = -1 ;        根本 也不需要 这个 变量
		int l = 0;
		int r = nums.length - 1;
		int mid = 0;
		while(l <= r) {
			mid = l + r >> 1;
			if(nums[mid] == target) {
				return mid;
			}
			else if(nums[mid] < target) {
				l = mid +1;
			}
			else {
				r = mid - 1;
			}
		}
		
		return -1;
	}
}
